package com.leetcode.partition14;

/**
 * @author `RKC`
 * @date 2021/10/27 20:09
 */
public class LC1319连通网络的操作次数 {

    public static int makeConnected(int n, int[][] connections) {
        //n个节点的最小连通图至少需要n-1条边
        if (connections.length < n - 1) return -1;
        UnionFind unionFind = new UnionFind(n);
        for (int[] connection : connections) {
            int id1 = connection[0], id2 = connection[1];
            if (!unionFind.isConnected(id1, id2)) {
                unionFind.union(id1, id2);
            }
        }
        //结果等于连通分量减1
        return unionFind.count - 1;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] connections = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}};
        System.out.println(makeConnected(n, connections));
    }

    private static class UnionFind {
        private final int[] ancestor;
        private int count;

        public UnionFind(int size) {
            ancestor = new int[size];
            //维护一个图中的连通分量
            count = size;
            for (int i = 0; i < ancestor.length; i++) ancestor[i] = i;
        }

        public int find(int x) {
            if (x == ancestor[x]) return x;
            int tempParent = find(ancestor[x]);
            ancestor[x] = tempParent;
            if (tempParent != ancestor[x]) count--;
            return ancestor[x];
        }

        public void union(int x, int y) {
            int parentX = find(x), parentY = find(y);
            if (parentX != parentY) {
                ancestor[parentY] = parentX;
                count--;
            }
        }

        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }
}
